//322.零钱兑换
//https://leetcode.cn/problems/coin-change/?envType=daily-question&envId=2024-03-24
class Solution {
    vector<int> cnt;
    //cnt[n]:代表数组中的硬币组成该数的最小数量 如果为-1则无法组成
    int dfs(vector<int>& coins, int amount)
    {
        if(amount < 0) return -1;
        if(amount == 0) return 0;
        if(cnt[amount] != 0) return cnt[amount];
        int num = INT_MAX;
        for(int m:coins)
        {
            int ret = dfs(coins,amount-m);
            //每次取最小组成结果 并将结果+1代表取当前硬币组成
            if(ret >= 0 && ret < num) num = ret+1;
        }
        //记忆化存储 如果当前数字无法被组成则-1
        cnt[amount] = num==INT_MAX?-1:num;
        return cnt[amount];
    }
public:
    int coinChange(vector<int>& coins, int amount) 
    {
        if(amount < 1) return 0;
        cnt.resize(amount+1);
        return dfs(coins,amount);
    }
};